package com.hard;

import java.util.LinkedList;

//https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solutions/213779/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/
public class SolutionLCR183 {
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights.length == 0) return new int[0];
        LinkedList<Integer> deque = new LinkedList<>();
        int[] res = new int[heights.length - limit + 1];
        for (int i = 1 - limit, j = 0; j < heights.length; i++, j++) {
            if (i > 0 && heights[i - 1] == deque.getFirst()) deque.removeFirst();
            while (!deque.isEmpty() && heights[j] > deque.getLast()) deque.removeLast();
            deque.addLast(heights[j]);
            if (i >= 0) res[i] = deque.getFirst();
        }
        return res;
    }
}
